﻿#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include "SequenceStackStore.h"
#include <stdbool.h>

struct BinNode
{
	char ch;
	struct BinNode* lChild;
	struct BinNode* rChild;
};
struct InfoBinTree
{
	struct BinNode* node;
	bool flag;
};
struct InfoBinTree* createInfoBinTree(struct BinNode* node, bool flag)
{
	struct InfoBinTree* info = malloc(sizeof(struct InfoBinTree));
	info->flag = flag;
	info->node = node;

	return info;
}
void nonRecurseTraverse(struct BinNode* root)
{
	//1.初始化栈；
	SeqStack stack = Init_SeqStack();
	//2.先把根节点压入栈中；
	Push_SeqStack(stack, createInfoBinTree(root, false));

	while (Size_SeqStack(stack) > 0)
	{
		//3.获得栈顶元素；
		struct InfoBinTree* info = (struct InfoBinTree*)Top_SeqStack(stack);
		//4.弹出栈顶元素；
		Pop_SeqStack(stack);

		if (info->flag)
		{
			printf("5.输出二叉树的节点元素：%c\n", info->node->ch);
			free(info);
			continue;
		}
		//11.后序遍历；
		info->flag = true;
		Push_SeqStack(stack, info);

		//6.将右子树压入栈中；
		if (info->node->rChild != NULL)
		{
			Push_SeqStack(stack, createInfoBinTree(info->node->rChild, false));
		}

		//10.中序遍历；
		//info->flag = true;
		//Push_SeqStack(stack, info);

		//7.将左子树压入栈中；
		if (info->node->lChild != NULL)
		{
			Push_SeqStack(stack, createInfoBinTree(info->node->lChild, false));
		}

		//8.将根节点压入栈中；右->左->根，出栈时，先进后出，即为先序遍历；
		//info->flag = true;
		//Push_SeqStack(stack, info);
	}

	//9.销毁栈；
	Destroy_SeqStack(stack);
}

void testBinaryTreeNon()
{
	struct BinNode nodeA = { 'A',NULL,NULL };
	struct BinNode nodeB = { 'B',NULL,NULL };
	struct BinNode nodeC = { 'C',NULL,NULL };
	struct BinNode nodeD = { 'D',NULL,NULL };
	struct BinNode nodeE = { 'E',NULL,NULL };
	struct BinNode nodeF = { 'F',NULL,NULL };
	struct BinNode nodeG = { 'G',NULL,NULL };
	struct BinNode nodeH = { 'H',NULL,NULL };

	nodeA.lChild = &nodeB;
	nodeA.rChild = &nodeF;

	nodeB.rChild = &nodeC;
	nodeC.lChild = &nodeD;
	nodeC.rChild = &nodeE;

	nodeF.rChild = &nodeG;
	nodeG.lChild = &nodeH;

	nonRecurseTraverse(&nodeA);//A,B,C,D,E,F,G,H --> B,D,C,E,A,F,H,G --> D,E,C,B,H,G,F,A
}

//main230：二叉树的非递归遍历
int main230()
{
	testBinaryTreeNon();

	system("pause");
	return EXIT_SUCCESS;
}